#include "lru.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
  int page;
  int last_used;
} Frame;

/**
 * 函数：模拟LRU页面置换算法。
 *
 * @param queue_frames 一个字符串，表示页面访问序列。
 *                     字符串中的每个字符是一个数字，表示一个页面号。
 * @param num   页框的数量，表示物理内存中可用的页框数。
 *
 * @return void - 为啥参数名字对不上呢？
 *
 * 吐槽：就连函数名字也是错的……
 */
void
lru_page_replacement (char *queue_frames, int num)
{
  // TODO
  Frame *frames = (Frame *)malloc (num * sizeof (Frame));
  for (int i = 0; i < num; i++)
    {
      frames[i].page = -1;
      frames[i].last_used = -1;
    }

  char *token = strtok (queue_frames, ",");
  int time = 0;
  while (token != NULL)
    {
      int page = atoi (token);
      time++;

      int found = -1;
      for (int i = 0; i < num; i++)
        {
          if (frames[i].page == page)
            {
              found = i;
              break;
            }
        }

      if (found != -1)
        {
          frames[found].last_used = time;
        }
      else
        {
          int lru_index = 0;
          for (int i = 1; i < num; i++)
            {
              if (frames[i].last_used < frames[lru_index].last_used)
                {
                  lru_index = i;
                }
            }
          frames[lru_index].page = page;
          frames[lru_index].last_used = time;
        }

      printf ("Access:%d,Frames: [", page);
      for (int i = 0; i < num; i++)
        {
          if (i != 0)
            printf (",");
          if (frames[i].page != -1)
            {
              printf ("%d", frames[i].page);
            }
          else
            {
              printf ("-1");
            }
        }
      printf ("]\n");

      token = strtok (NULL, ",");
    }

  free (frames);
}
